// 递归实现
function dfs(root) {
  let res = []
  if (root) {
    res.push(root.val)
    if (root.left) res.push(...dfs(root.left))
    if (root.right) res.push(...dfs(root.right))
  }
  return res
}

// 非递归实现
function DFS(root) {
  let res = []
  if (root) {
    let stack = [root]
    while (stack.length > 0) {
      let cur = stack.pop()
      res.push(cur.val)
      if (cur.right) stack.push(cur.right)
      if (cur.left) stack.push(cur.left)
    }

  }
  return res
}



function BFS(root) {
  let res = []
  if (root) {
    let queue = [root]
    while (queue.length > 0) {
      let cur = queue.shift()
      res.push(cur.val)
      if (cur.left) queue.push(cur.left)
      if (cur.right) queue.push(cur.right)
    }
  }
  return res
}
let root = getTreeFromLayerOrderArray([1, 2, 3, null, 4, 5, 6])
console.log(dfs(root))
console.log(DFS(root))
console.log(BFS(root))
function TreeNode(val, left = null, right = null) {
  this.val = val;
  this.left = left;
  this.right = right;
}
/**
* 通过一个层次遍历的数组生成一棵二叉树
* @param {any[]} array
* @return {TreeNode}
*/
function getTreeFromLayerOrderArray(array) {
  let n = array.length;
  if (!n) return null;
  let index = 0;
  let root = new TreeNode(array[index++]);
  let queue = [root];
  while (index < n) {
    let top = queue.shift();
    let v = array[index++];
    top.left = v == null ? null : new TreeNode(v);
    if (index < n) {
      let v = array[index++];
      top.right = v == null ? null : new TreeNode(v);
    }
    if (top.left) queue.push(top.left);
    if (top.right) queue.push(top.right);
  }
  return root;
}
/**
* 层序遍历一棵二叉树 生成一个数组
* @param {TreeNode} root 
* @return {any[]}
*/
function getLayerOrderArrayFromTree(root) {
  let res = [];
  let que = [root];
  while (que.length) {
    let len = que.length;
    for (let i = 0; i < len; i++) {
      let cur = que.shift();
      if (cur) {
        res.push(cur.val);
        que.push(cur.left, cur.right);
      } else {
        res.push(null);
      }
    }
  }
  while (res.length > 1 && res[res.length - 1] == null) res.pop(); // 删掉结尾的 null
  return res;
}